1. Field of the Invention
This disclosure relates generally to data encoding, storage, distribution, and decoding, and more particularly but not exclusively, to n dimensional signal sequence encoding, storage, distribution, and decoding by use of an n dimensional block matching prediction method.
2. Description of the Prior Art
Digital data systems are frequently challenged to handle large quantities of data quickly enough to meet practical needs. Compact disc music requires about 1500 kilobits per second, and video needs over 200,000 kilobits per second. Both transmission and storage of data is costly, and in some cases impossible. For example, a current telephone line modem can only carry maximum bit rate at 56 kilobits per second with a perfect line condition. Although video image frames need only be handled at approximately 30 cycles per second in order to allow an observer to have the impression of continual image transmission, the data content of each image frame is very large.
Solutions to the problem of quickly handling large quantities of data have been developed by using methods of data compression, i.e., methods of reducing the quantity of bits required. Data compression has made possible technological developments including digital television, DVD movie, streaming Internet video, home digital photography and video conferencing. Compressing coders and decoders (CODECs) are used to encode (at the capturing/production side) and decode (at the receiving/reproduction side) data containing statistical redundancy (as taught in chapter 3 of the book by Iain E. G. Richardson, entitled H. 264 and MPEG-4 Video Compression—Video Coding for Next-Generation Multimedia, published by John Wiley & Sons, Ltd., 2003, which is hereby incorporated by reference).
FIG. 1A is a simplified block diagram for describing a prior art method for compression of image sequence data with an encoder. This system includes an input image frame 4, a discrete cosine transform (DCT) 14, a quantizer Q module 15, a run-level coding module 19, a VLC entropy coding module 20, a motion estimation search (ME) module 5, a difference energy based cost function calculator 13, and a decoder 10. The decoder 10 includes a motion compensation module (MC) 11, an inverse DCT module T−1 12, and a frame buffer 3 for one or more frames. The motion compensation (MC) module 11 produces a motion compensated prediction (MCP) 17, which provides one of the inputs for the frame buffer 3 and discrete cosine transform (DCT) module 14. The motion estimation search (ME) module 5 outputs a motion vector MV 7 to both the VLC entropy coding module 20 and the motion compensation (MC) module 11. The motion estimation search (ME) module 5 also receives as inputs the input image frame 4, the decoded reference frame 6, to search for the best location from the reference frame(s) according to certain cost function. At each search point, ME module 5 sends the information 21 about the current block and target block at the search point to the cost function calculator 13, and receives the calculated cost value 22 from the difference energy based cost function calculator 13. After the search, the motion estimation search (ME) module 5 outputs a motion vector MV 7 to both the VLC entropy coding module 20 and the motion compensation (MC) module 11.
An image frame is input to the encoder 1 and the data is encoded. The encoded frame 2 is then transmitted to a transmission channel or storage media (not shown), and a copy of the encoded frame is decoded at the decoder 10 and stored as a reference frame in the frame buffer 3. The next, current input image frame 4 is then input to the encoder 1. The encoder 1 then searches the reference frame 6 for a closest match point in the reference frame for each block of a plurality of blocks that make up the current frame, using the motion estimation search (ME) module 5, by calculating what is termed an “energy difference” measure, such as sum of square error or sum of absolute error between the current frame block and corresponding reference frame block located at each search point in the reference frame. The best matched location is then represented as a “motion vector” 7, specifying the two dimensional location displacement of the block in the reference frame relative to the corresponding block in the current frame. Also, the difference 8 between the best match blocks in the reference frame and the current frame is determined. This difference 8 is called the “Block Prediction Difference” (BPD), or “Residue 8.” Both the motion vector 7 and the residue 8 are then encoded and transmitted. The encoder 1 will then also decode the motion vector 7 and residue 8 and reconstruct the current frame in the same way that a decoder to which the data is sent would reconstruct the frame, and then store this frame as a reference frame. The prior art describes variations for the simplified process described in FIG. 1A.
A very significant issue is the amount of computational power that is required by the encoder in accomplishing the task of finding the best match for each block in the current frame, i.e., determining the displacement vector such that the displacement block in the reference frame is most “similar” to the current block. One prior art method of performing this task involves searching every possible block location within a pre-defined search area. This method requires astronomical computing power and is not feasible for practical real time implementation. There are many simplified methods to search a fraction of the large and complete search space to reduce the computation cost. However, the simplified methods usually have significant quality loss of the encoded video related to the “full search” encoder, and cannot provide consistent compression quality close to the “full search” encoder on all real life cases. Furthermore, all of the search methods in the prior art (including the full search method) select the best match block location primarily by calculating some type of “energy difference” measure, such as the “sum of square error”, or “sum of absolute error” between pixels of the block in the current frame and the block at each search location in the reference frame. In general, the target of the encoder is to minimize the bit rate to achieve certain acceptable quality. The currently used “energy difference” based measure does not necessarily give the best quality and bit rate in the encoded image sequence. What is needed is an improved data compression and motion estimation technology which can achieve minimized bit rate with good quality with practical and efficient computing cycles.